package com.sicheng.datastruct.tree.utils;

import com.sicheng.datastruct.tree.HeroNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/27 17:05
 */

@SuppressWarnings("unused")
public class TreeUtil {
    public static void swap(HeroNode root) {
        if (root == null)
            return;
        HeroNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

    public static boolean isSymmetrical(HeroNode root) {

        if (root == null)
            return false;

        return isSymmetrical(root.left, root.right);
    }

    // 对称的二叉树
    public static boolean isSymmetrical(HeroNode left, HeroNode right) {

        if (left == null && right == null)
            return true;
        if (left == null || right == null)
            return false;
        if (left.no != right.no)
            return false;

        return isSymmetrical(left.left, right.right) && isSymmetrical(left.right, right.left);

    }

    // 层次遍历二叉树
    public static void levelTraversal(HeroNode root) {
        int[] tree = treeToArr(root);
        System.out.println(Arrays.toString(tree));
    }

    // 树的结点树，size
    public static int sizeOfTree(HeroNode root) {
        if (root == null)
            return 0;

        else
            return sizeOfTree(root.left) + 1 + sizeOfTree(root.right);
    }

    public static int[] treeToArr(HeroNode root) {
        int sizeOfTree = sizeOfTree(root);
        if (sizeOfTree == 0)
            return null;
        if (sizeOfTree == 1)
            return new int[root.no];
        int[] tree = new int[sizeOfTree];
        treeToArr(root, tree, 0);
        return tree;
    }

    private static void treeToArr(HeroNode root, int[] tree, int n) {
        if (root == null)
            return;

        tree[n] = root.no;

        if (2 * n + 1 < tree.length)
            treeToArr(root.left, tree, 2 * n + 1);
        if (2 * n + 2 < tree.length)
            treeToArr(root.right, tree, 2 * n + 2);
    }

    public static List<Integer> listFromTopToBottom(HeroNode root) {
        if (root == null)
            return null;
        LinkedList<HeroNode> seeds = new LinkedList<>();

        ArrayList<Integer> nodes = new ArrayList<>();
        seeds.add(root);
        while (seeds.size() > 0) {
            HeroNode seed = seeds.poll();
            if (seed == null)
                continue;

            seeds.add(seed.left);
            seeds.add(seed.right);
            nodes.add(seed.no);


        }

        return nodes;

    }


}
